하노이의 탑 - Lv.2

문제

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

• 한 번에 하나의 원판만 옮길 수 있습니다.
• 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

n은 15이하의 자연수 입니다.

입출력 예

n result 2 [ [1,2], [1,3], [2,3] ]

구조

이것은 단계적이고 체계적인 분류와 분기 조건 확인이 필요한 문제는 아니다. 대신 주어진 조건대로 재귀를 구현하는 것이 문제이다. 하지만 이 조건만으로 구조를 파악하기 쉽지가 않다.

단계적으로 풀어가 보자.

• N개의 크기 차이가 있는 큰 것부터 바닥에 쌓은 원판들을 옮긴다.
• 기둥은 3개가 있다.
• 1->3일 시 보조기둥이 필요하다.
• 원판은 자신보다 큰 원판 위에 올라가지 않는다
  • 모든 원판은 시작 시 가장 왼쪽의 기둥에 모여 있다.

이는 단순히 어떤 보조 기둥을 거쳐 원판을 어떤 목적지로 옮기느냐의 문제로 귀결된다.

그렇다면 문제의 케이스는 둘로 좁힐 수 있다.

• 보조 기둥이 없을 시 (보조 기둥 == 목적지)
• 보조 기둥이 있을 시 (보조 기둥 != 목적지) 그러나 보조 기능을 사용하는 케이스와 사용하지 않는 케이스는 이 문제에서 요구하는, 출발지점-목적지 구조에서 보조 기둥을 사용한 것과 완벽히 동일하게 간주된다.

그렇다면 보조 기둥을 강제하면 된다.

그러나 이것의 케이스를 둘로 나누어야 한다.

• 출발지 - 보조 기둥 (최종 목적지를 보조 기둥처럼 사용)
• 보조 기둥 - 목적지 (출발지를 보조 기둥처럼 사용

이것은 출발지 - 목적지만 담는 출제 의도에선 사소한 사항인 것이다.

이렇게 구현 방법을 단순화하였으니. 이 부분이 pt1, pt2로 표기된 것을 유심히 보며 코드를 보도록 하자.

풀이

#include <string>
#include <vector>

using namespace std;

void hanoi(vector<vector<int>> &answer, int n, int from, int to, int via) {
    if(n==1) {
        answer.push_back({from, to});
        return;
    }
    hanoi(answer, n-1/*smaller recursion*/, from, via, to); // pt1. from -> via using to
    answer.push_back({from, to});
    hanoi(answer, n-1 /*smaller recursion*/, via, to, from); // pt2. via -> to using from
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    hanoi(answer, n, 1, 3, 2);
    return answer;
}

재귀적 사고를 요구하는 문제이다. 아마도 중견기업, 대기업, 기술 위주 스타트업 문제에 중급 문제로 출제될 수 있는 유형같다.